BZOJ 2738 矩阵乘法

Description

给你一个N*N的矩阵,不用算矩阵乘法,但是每次询问一个子矩形的第K小数。

Input

第一行两个数N,Q,表示矩阵大小和询问组数;
接下来N行N列一共N*N个数,表示这个矩阵; 再接下来Q行每行5个数描述一个询问:x1,y1,x2,y2,k表示找到以(x1,y1)为左上角、以(x2,y2)为右下角的子矩形中的第K小数。

Output

对于每组询问输出第K小的数。

Sample Input

2 2
2 1
3 4
1 2 1 2 1
1 1 2 2 3

Sample Output

1
3

Hint

矩阵中数字是109以内的非负整数;
20%的数据:N<=100,Q<=1000;
40%的数据:N<=300,Q<=10000;
60%的数据:N<=400,Q<=30000;
100%的数据:N<=500,Q<=60000。

Solution

整体二分+二位树状数组
貌似挺水

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
#include<bits/stdc++.h>

#define maxn 500+5
#define maxk 60000+5
#define maxm 250000+5
#define set(a,b) memset(a,(b),sizeof(a))

using namespace std;

typedef long long ll;

struct gribs{
int x,y,k;
}grib[maxm];

struct option{
int x1,y1,x2,y2,k,id;
}op[maxk],sup[maxk];

int bit[maxn][maxn],sp[maxn][maxn];
int blg[maxm],timer,tot;
int n,m,ans[maxk];

bool comp(gribs a,gribs b)
{

return a.k<b.k;
}

void add(int x,int y,int w)
{

for(int i=x;i<=n;i+=i&-i)
for(int j=y;j<=n;j+=j&-j)
if( sp[i][j]==timer ) bit[i][j]+=w;
else sp[i][j]=timer,bit[i][j]=w;
}

int sum(int x,int y)
{

int res=0;
for(int i=x;i;i-=i&-i)
for(int j=y;j;j-=j&-j)
if( sp[i][j]==timer ) res+=bit[i][j];
return res;
}

void solve(int l,int r,int L,int R)
{

if( L>R ) return ;
if( l==r ){
for(int i=L;i<=R;i++) ans[op[i].id]=grib[l].k;
return ;
}
timer++;
for(int i=l;i<=(l+r)/2;i++)
add(grib[i].x,grib[i].y,1);
int ls=0,rs=0,cnt=0;
for(int i=L;i<=R;i++){
int res=sum(op[i].x2,op[i].y2)+sum(op[i].x1-1,op[i].y1-1)-sum(op[i].x1-1,op[i].y2)-sum(op[i].x2,op[i].y1-1);
if( res>=op[i].k ) blg[i]=0,cnt++;
else blg[i]=1,op[i].k-=res;
sup[i]=op[i];
}
for(int i=L;i<=R;i++)
if( blg[i]==0 ) op[L+ls++]=sup[i];
else op[L+cnt+rs++]=sup[i];
solve(l,(l+r)/2,L,L+cnt-1),solve((l+r)/2+1,r,L+cnt,R);
}

int main()
{

#ifndef ONLINE_JUDGE
freopen("2738.in","r",stdin);
freopen("2738.out","w",stdout);
#endif
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++){
int k;
scanf("%d",&k);
grib[++tot]=(gribs){i,j,k};
}
for(int i=1;i<=m;i++){
scanf("%d%d%d%d%d",&op[i].x1,&op[i].y1,&op[i].x2,&op[i].y2,&op[i].k);
op[i].id=i;
}
sort(grib+1,grib+tot+1,comp);
solve(1,tot,1,m);
for(int i=1;i<=m;i++)
printf("%d\n",ans[i]);
return 0;
}